package com.ds.bintree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/10/12 20:14
 */

/**
 * 定义二叉树的结点
 */
class TreeNode<E>{
    E val;
    TreeNode<E> left;
    TreeNode<E> right;

    TreeNode(E val){
        this.val = val;
    }
}


public class MyBinTree<E> {
    /**
     * 构建一颗二叉树
     */
    public TreeNode<Character> root;

    public TreeNode<Character> build() {
        TreeNode<Character> node = new TreeNode<>('A');
        TreeNode<Character> node1 = new TreeNode<>('B');
        TreeNode<Character> node2 = new TreeNode<>('C');
        TreeNode<Character> node3 = new TreeNode<>('D');
        TreeNode<Character> node4 = new TreeNode<>('E');
        TreeNode<Character> node5 = new TreeNode<>('F');
        TreeNode<Character> node6 = new TreeNode<>('G');
        TreeNode<Character> node7 = new TreeNode<>('H');
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node4.left = node6;
        node6.right = node7;
        node2.right = node5;
        root = node;
        return root;
    }

    /**
     * 传入一颗二叉树的根节点root。就能按照前序遍历根左右的方式进行输出
     *
     * @param root
     */
    public void preOrder(TreeNode<?> root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
     * 传入一颗二叉树的根节点root。就能按照中序遍历左根右的方式进行输出
     *
     * @param root
     */
    public void inOrder(TreeNode<?> root) {
        if (root == null) {
            return;
        }
        // 先打印左子树,交给子函数
        inOrder(root.left);
        // 打印根
        System.out.print(root.val + " ");
        // 最后打印右子树
        inOrder(root.right);
    }


    /**
     * 传入一颗二叉树的根节点root。就能按照后序遍历左右根的方式进行输出
     *
     * @param root
     */
    public void postOrder(TreeNode<?> root) {
        if (root == null) {
            return;
        }
        // 先打印左子树,交给子函数
        postOrder(root.left);
        // 再打印右子树
        postOrder(root.right);
        // 最后打印根
        System.out.print(root.val + " ");
    }

    /**
     * 求出以root为根的二叉树，就能求出结点为多少
     *
     * @param root
     * @return
     */
    public int getNodes(TreeNode<?> root) {
        return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);
    }


    /**
     * 层序遍历二叉树的结点数
     *
     * @param root
     * @return
     */
    public int getNodesNonRecursion(TreeNode<?> root) {
        if (root == null) {
            return 0;
        }
        Deque<TreeNode<?>> queue = new LinkedList<>();
        queue.offer(root);
        int num = 0;
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            num++;
            if (temp.left != null) {
                queue.offer(temp.left);
            }
            if (temp.right != null) {
                queue.offer(temp.right);
            }
        }
        return num;
    }

    /**
     * 传入以root为根的树，就能求出叶子节点个数
     *
     * @param root
     * @return
     */
    public int getLeafNodes(TreeNode<?> root) {
        // 1.边界
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            // 只有root,root就是一个叶子结点
            return 1;
        }
        // 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }


    /**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     *
     * @return
     */
    public int getKLevelNodes(TreeNode root, int k) {
        // 1.边界条件
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

    /**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     *
     * @param root
     * @return
     */
    public int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }

    /**
     * 判断以root为根的二叉树中是否包含指定值val
     *
     * @param root
     * @param val
     * @return
     */
    public boolean contains(TreeNode<E> root, E val) {
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }
        // 继续在左子树和右子树中寻找是否包含指定值
        return contains(root.left, val) || contains(root.right, val);
    }

    /**
     *  借助队列，实现二叉树的层序遍历
     * @param root
     */
    public void levelOrder(TreeNode<E> root) {
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        // 循环的终止条件就是队列为空
        while (!queue.isEmpty()) {
            // 取出当前层的节点个数，每当进行下一次遍历的时候，队列中就存储了该层的所有元素
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode<E> node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }
}